// Go作者版权所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

import (
	"fmt"
)

type loop struct {
	header *Block // 此（可还原）循环的头节点
	outer  *loop  // 包含此循环的循环

	// 默认情况下，不会初始化子级、出口和深度。
	children []*loop  // 直接嵌套在此循环中的循环。已由assembleChildren（）初始化。
	exits    []*Block // exits记录此循环的出口到达的块。由findExits（）初始化。

	// regalloc和/或使用的下三个字段
	// 帮助计算内部粗糙度和块列表。
	nBlocks int32 // 此循环中但不在内部循环中的块数
	depth   int16 // 环的嵌套深度；1是最外层的。已由calculateDepths（）初始化。
	isInner bool  // 如果从未发现包含循环，则为True

	// 寄存器分配使用这个函数。
	containsUnavoidableCall bool // 如果通过循环的所有路径都有调用，则为True
}

// outerinner记录外部包含内部
func (sdom SparseTree) outerinner(outer, inner *loop) {
	// 可能还有其他随机排列的外环，
	// 在它们之间适当地定位新的外环。

	// 外部循环头控制内部循环头。
	// 使用此选项将“新”“外部”回路放置在正确的位置。
	oldouter := inner.outer
	for oldouter != nil && sdom.isAncestor(outer.header, oldouter.header) {
		inner = oldouter
		oldouter = inner.outer
	}
	if outer == oldouter {
		return
	}
	if oldouter != nil {
		sdom.outerinner(oldouter, outer)
	}

	inner.outer = outer
	outer.isInner = false
}

func checkContainsCall(bb *Block) bool {
	if bb.Kind == BlockDefer {
		return true
	}
	for _, v := range bb.Values {
		if opcodeTable[v.Op].call {
			return true
		}
	}
	return false
}

type loopnest struct {
	f              *Func
	b2l            []*loop
	po             []*Block
	sdom           SparseTree
	loops          []*loop
	hasIrreducible bool // 当前对不可约循环的处理是非常脆弱的，如果需要精确的循环，则必须在函数级别上进行。

	// 记录哪些延迟初始化的字段实际已初始化。
	initializedChildren, initializedDepth, initializedExits bool
}

func min8(a, b int8) int8 {
	if a < b {
		return a
	}
	return b
}

func max8(a, b int8) int8 {
	if a > b {
		return a
	}
	return b
}

const (
	blDEFAULT = 0
	blMin     = blDEFAULT
	blCALL    = 1
	blRET     = 2
	blEXIT    = 3
)

var bllikelies = [4]string{"default", "call", "ret", "exit"}

func describePredictionAgrees(b *Block, prediction BranchPrediction) string {
	s := ""
	if prediction == b.Likely {
		s = " (agrees with previous)"
	} else if b.Likely != BranchUnknown {
		s = " (disagrees with previous, ignored)"
	}
	return s
}

func describeBranchPrediction(f *Func, b *Block, likely, not int8, prediction BranchPrediction) {
	f.Warnl(b.Pos, "Branch prediction rule %s < %s%s",
		bllikelies[likely-blMin], bllikelies[not-blMin], describePredictionAgrees(b, prediction))
}

func likelyadjust(f *Func) {
	// 分配给特定和局部的值只起作用
	// 按照他们的等级顺序。0是默认值，更积极
	// 可能性不大。可以指定一个负数
	// 不太可能（尽管目前情况并非如此）。
	certain := make([]int8, f.NumBlocks()) // 从长远来看，所有结果都至少如此糟糕。主要用于出口
	local := make([]int8, f.NumBlocks())   // 为了我们的前辈。

	po := f.postorder()
	nest := f.loopnest()
	b2l := nest.b2l

	for _, b := range po {
		switch b.Kind {
		case BlockExit:
			// 不太可能。
			local[b.ID] = blEXIT
			certain[b.ID] = blEXIT

			// 雷特，这要看情况。
		case BlockRet, BlockRetJmp:
			local[b.ID] = blRET
			certain[b.ID] = blRET

			// 电话。TODO并非所有的呼叫都是相等的，名称提供了有用的线索。
			// 任何基于名称的启发式都只与其他调用相关，
			// 比从循环结构推断的影响小。
		case BlockDefer:
			local[b.ID] = blCALL
			certain[b.ID] = max8(blCALL, certain[b.Succs[0].b.ID])

		default:
			if len(b.Succs) == 1 {
				certain[b.ID] = certain[b.Succs[0].b.ID]
			} else if len(b.Succs) == 2 {
				// 若继任者是一个未访问的后缘，它在循环中，我们不在乎。
				// 其默认值也为零，这与偏好循环边一致。
				// 请注意，这可能会像“重置”循环中的不可能性一样；这个
				// 默认的“一切都返回”不可能由min用
				// 后缘相似性；但是，每个路径上都有调用的循环将被禁用
				// 标记了通话费用。最终的效果是循环入口更受欢迎。
				b0 := b.Succs[0].b.ID
				b1 := b.Succs[1].b.ID
				certain[b.ID] = min8(certain[b0], certain[b1])

				l := b2l[b.ID]
				l0 := b2l[b0]
				l1 := b2l[b1]

				prediction := b.Likely
				// 弱循环启发式——源和至少一个目标都在循环中，
				// 而且目的地也不同。
				// TODO嵌套循环的最佳排列是什么？
				if l != nil && l0 != l1 {
					noprediction := false
					switch {
					// 不要退出循环
					case l1 == nil:
						prediction = BranchLikely
					case l0 == nil:
						prediction = BranchUnlikely

						// 宁愿留在循环中，而不是退出到外部。
					case l == l0:
						prediction = BranchLikely
					case l == l1:
						prediction = BranchUnlikely
					default:
						noprediction = true
					}
					if f.pass.debug > 0 && !noprediction {
						f.Warnl(b.Pos, "Branch prediction rule stay in loop%s",
							describePredictionAgrees(b, prediction))
					}

				} else {
					// 由于缺乏循环结构，只能依靠启发式。
					if certain[b1] > certain[b0] {
						prediction = BranchLikely
						if f.pass.debug > 0 {
							describeBranchPrediction(f, b, certain[b0], certain[b1], prediction)
						}
					} else if certain[b0] > certain[b1] {
						prediction = BranchUnlikely
						if f.pass.debug > 0 {
							describeBranchPrediction(f, b, certain[b1], certain[b0], prediction)
						}
					} else if local[b1] > local[b0] {
						prediction = BranchLikely
						if f.pass.debug > 0 {
							describeBranchPrediction(f, b, local[b0], local[b1], prediction)
						}
					} else if local[b0] > local[b1] {
						prediction = BranchUnlikely
						if f.pass.debug > 0 {
							describeBranchPrediction(f, b, local[b1], local[b0], prediction)
						}
					}
				}
				if b.Likely != prediction {
					if b.Likely == BranchUnknown {
						b.Likely = prediction
					}
				}
			}
			// 在街区里找电话。如果有，则不太可能出现这种情况。
			for _, v := range b.Values {
				if opcodeTable[v.Op].call {
					local[b.ID] = blCALL
					certain[b.ID] = max8(blCALL, certain[b.Succs[0].b.ID])
					break
				}
			}
		}
		if f.pass.debug > 2 {
			f.Warnl(b.Pos, "BP: Block %s, local=%s, certain=%s", b, bllikelies[local[b.ID]-blMin], bllikelies[certain[b.ID]-blMin])
		}

	}
}

func (l *loop) String() string {
	return fmt.Sprintf("hdr:%s", l.header)
}

func (l *loop) LongString() string {
	i := ""
	o := ""
	if l.isInner {
		i = ", INNER"
	}
	if l.outer != nil {
		o = ", o=" + l.outer.header.String()
	}
	return fmt.Sprintf("hdr:%s%s%s", l.header, i, o)
}

func (l *loop) isWithinOrEq(ll *loop) bool {
	if ll == nil { // 零表示整个程序
		return true
	}
	for ; l != nil; l = l.outer {
		if l == ll {
			return true
		}
	}
	return false
}

// nearestOuterLoop返回最接近loop的外部循环
// 包含块b；头球必须控制b。循环本身
// 假设不是那个循环。对于可接受的性能，
// 我们依靠的是环巢不会太深。
func (l *loop) nearestOuterLoop(sdom SparseTree, b *Block) *loop {
	var o *loop
	for o = l.outer; o != nil && !sdom.IsAncestorEq(o.header, b); o = o.outer {
	}
	return o
}

func loopnestfor(f *Func) *loopnest {
	po := f.postorder()
	sdom := f.Sdom()
	b2l := make([]*loop, f.NumBlocks())
	loops := make([]*loop, 0)
	visited := make([]bool, f.NumBlocks())
	sawIrred := false

	if f.pass.debug > 2 {
		fmt.Printf("loop finding in %s\n", f.Name)
	}

	// 可约循环嵌套查找。
	for _, b := range po {
		if f.pass != nil && f.pass.debug > 3 {
			fmt.Printf("loop finding at %s\n", b)
		}

		var innermost *loop // 可从此块访问的最内层标头

		// 如果b的任何后继s在以h为首的循环中
		// h支配b
		// 然后b在以h为首的循环中。
		// None
		// 选择第一个/最里面的h。
		// None
		// 如果s本身支配b，则s是循环头；
		// 而且可能有不止一个这样的s。
		// 因为最多有两个继承者，所以内部/外部顺序
		// 可以通过简单的比较来确定它们之间的关系。
		for _, e := range b.Succs {
			bb := e.b
			l := b2l[bb.ID]

			if sdom.IsAncestorEq(bb, b) { // 找到一个循环头
				if f.pass != nil && f.pass.debug > 4 {
					fmt.Printf("loop finding    succ %s of %s is header\n", bb.String(), b.String())
				}
				if l == nil {
					l = &loop{header: bb, isInner: true}
					loops = append(loops, l)
					b2l[bb.ID] = l
				}
			} else if !visited[bb.ID] { // 找到了一个不可约的循环
				sawIrred = true
				if f.pass != nil && f.pass.debug > 4 {
					fmt.Printf("loop finding    succ %s of %s is IRRED, in %s\n", bb.String(), b.String(), f.Name)
				}
			} else if l != nil {
				// 处理l不可约的情况。
				// 也许循环头是继承的。
				// 是否存在包含我们的继任者的循环
				// 头球控制b？
				if !sdom.IsAncestorEq(l.header, b) {
					l = l.nearestOuterLoop(sdom, b)
				}
				if f.pass != nil && f.pass.debug > 4 {
					if l == nil {
						fmt.Printf("loop finding    succ %s of %s has no loop\n", bb.String(), b.String())
					} else {
						fmt.Printf("loop finding    succ %s of %s provides loop with header %s\n", bb.String(), b.String(), l.header.String())
					}
				}
			} else { // 无回路
				if f.pass != nil && f.pass.debug > 4 {
					fmt.Printf("loop finding    succ %s of %s has no loop\n", bb.String(), b.String())
				}

			}

			if l == nil || innermost == l {
				continue
			}

			if innermost == nil {
				innermost = l
				continue
			}

			if sdom.isAncestor(innermost.header, l.header) {
				sdom.outerinner(innermost, l)
				innermost = l
			} else if sdom.isAncestor(l.header, innermost.header) {
				sdom.outerinner(l, innermost)
			}
		}

		if innermost != nil {
			b2l[b.ID] = innermost
			innermost.nBlocks++
		}
		visited[b.ID] = true
	}

	ln := &loopnest{f: f, b2l: b2l, po: po, sdom: sdom, loops: loops, hasIrreducible: sawIrred}

	// 计算容器避免调用regalloc
	dominatedByCall := make([]bool, f.NumBlocks())
	for _, b := range po {
		if checkContainsCall(b) {
			dominatedByCall[b.ID] = true
		}
	}
	// 运行dfs以查找循环中避免所有调用的路径。
	// 这样的路径要么跳出循环，要么返回到报头。
	// 让退出不受任何调用控制是不够的，例如：
	// ... 一些循环
	// 呼叫1呼叫2
	// \      /
	// 出口
	// ...
	// 退出不受任何呼叫控制，但我们没有无呼叫路径。
	for _, l := range loops {
		// 标题包含调用。
		if dominatedByCall[l.header.ID] {
			l.containsUnavoidableCall = true
			continue
		}
		callfreepath := false
		tovisit := make([]*Block, 0, len(l.header.Succs))
		// 将标题的所有非循环非退出后续项推送到toVisit上。
		for _, s := range l.header.Succs {
			nb := s.Block()
			// 这对应于零迭代的循环。
			if !l.iterationEnd(nb, b2l) {
				tovisit = append(tovisit, nb)
			}
		}
		for len(tovisit) > 0 {
			cur := tovisit[len(tovisit)-1]
			tovisit = tovisit[:len(tovisit)-1]
			if dominatedByCall[cur.ID] {
				continue
			}
			// 在DominedByCall中访问的记录。
			dominatedByCall[cur.ID] = true
			for _, s := range cur.Succs {
				nb := s.Block()
				if l.iterationEnd(nb, b2l) {
					callfreepath = true
				}
				if !dominatedByCall[nb.ID] {
					tovisit = append(tovisit, nb)
				}

			}
			if callfreepath {
				break
			}
		}
		if !callfreepath {
			l.containsUnavoidableCall = true
		}
	}

	// 对这种循环感到好奇吗？“-d=ssa/likelyadjust/stats”
	if f.pass != nil && f.pass.stats > 0 && len(loops) > 0 {
		ln.assembleChildren()
		ln.calculateDepths()
		ln.findExits()

		// 注意：非最内层循环的统计数据有轻微缺陷，因为
		// 它们不考虑跨多个级别的内部循环出口。

		for _, l := range loops {
			x := len(l.exits)
			cf := 0
			if !l.containsUnavoidableCall {
				cf = 1
			}
			inner := 0
			if l.isInner {
				inner++
			}

			f.LogStat("loopstats:",
				l.depth, "depth", x, "exits",
				inner, "is_inner", cf, "always_calls", l.nBlocks, "n_blocks")
		}
	}

	if f.pass != nil && f.pass.debug > 1 && len(loops) > 0 {
		fmt.Printf("Loops in %s:\n", f.Name)
		for _, l := range loops {
			fmt.Printf("%s, b=", l.LongString())
			for _, b := range f.Blocks {
				if b2l[b.ID] == l {
					fmt.Printf(" %s", b)
				}
			}
			fmt.Print("\n")
		}
		fmt.Printf("Nonloop blocks in %s:", f.Name)
		for _, b := range f.Blocks {
			if b2l[b.ID] == nil {
				fmt.Printf(" %s", b)
			}
		}
		fmt.Print("\n")
	}
	return ln
}

// assembleChildren初始化每个
// 在巢里打圈。如果A是，则循环A是循环B的子循环
// 直接嵌套在B中（基于可约循环
// 检测（如上所述）
func (ln *loopnest) assembleChildren() {
	if ln.initializedChildren {
		return
	}
	for _, l := range ln.loops {
		if l.outer != nil {
			l.outer.children = append(l.outer.children, l)
		}
	}
	ln.initializedChildren = true
}

// CalculateDepth使用循环的子字段
// 要确定每个组件的嵌套深度（外部=1）
// 环这有助于查找出口边。
func (ln *loopnest) calculateDepths() {
	if ln.initializedDepth {
		return
	}
	ln.assembleChildren()
	for _, l := range ln.loops {
		if l.outer == nil {
			l.setDepth(1)
		}
	}
	ln.initializedDepth = true
}

// findExits使用循环深度信息来查找
// 从循环中退出。
func (ln *loopnest) findExits() {
	if ln.initializedExits {
		return
	}
	ln.calculateDepths()
	b2l := ln.b2l
	for _, b := range ln.po {
		l := b2l[b.ID]
		if l != nil && len(b.Succs) == 2 {
			sl := b2l[b.Succs[0].b.ID]
			if recordIfExit(l, sl, b.Succs[0].b) {
				continue
			}
			sl = b2l[b.Succs[1].b.ID]
			if recordIfExit(l, sl, b.Succs[1].b) {
				continue
			}
		}
	}
	ln.initializedExits = true
}

// 深度返回块b的循环嵌套级别。
func (ln *loopnest) depth(b ID) int16 {
	if l := ln.b2l[b]; l != nil {
		return l.depth
	}
	return 0
}

// recordIfExit检查sl（包含b的循环）是否
// 在循环l之外，如果是，则将b记录为退出块
// 从l返回，返回true。
func recordIfExit(l, sl *loop, b *Block) bool {
	if sl != l {
		if sl == nil || sl.depth <= l.depth {
			l.exits = append(l.exits, b)
			return true
		}
		// sl不是零，并且比l深
		// 这有可能是一个goto，变成一个由goto构成的不可约循环。
		for sl.depth > l.depth {
			sl = sl.outer
		}
		if sl != l {
			l.exits = append(l.exits, b)
			return true
		}
	}
	return false
}

func (l *loop) setDepth(d int16) {
	l.depth = d
	for _, c := range l.children {
		c.setDepth(d + 1)
	}
}

// iterationEnd检查块b是否结束循环l的迭代。
// 结束迭代意味着要么转义到外部循环/代码，要么
// 返回页眉
func (l *loop) iterationEnd(b *Block, b2l []*loop) bool {
	return b == l.header || b2l[b.ID] == nil || (b2l[b.ID] != l && b2l[b.ID].depth <= l.depth)
}
